1. Field of Invention
The present invention relates in general to the field of networking. More specifically, embodiments of the present invention provide systems and methods for managing multiple instances of a network topology.
2. Description of the Background Art
Computer interconnection and communication systems or “networks” have moved beyond traditional limitations to include more capable interconnection possibilities. A traditional local area network (LAN), for example, includes a shared, limited-bandwidth transmission medium that interconnects a limited number of devices (stations) over a small area. Each station has a fixed, globally unique address (unique identifier or UID), and communicates by sending and receiving data packets or groups of data packets. Data packets (packets) generally include a packet source address UID, a packet destination address UID and a payload, and the destination address typically includes a station address UID, a group address UID (multicast packet type) or a group address of all interconnected stations (broadcast packet type). More extensive network types, such as metropolitan area networks (MANs), wide area networks (WANs), and so on, can operate in a similar manner and can similarly comprise a linear, ring or multiple redundant (e.g., star, mesh, etc.) configuration.
LANs, however, provide useful high-speed communication services that facilitate data sharing, client-server or other interactions among its stations. LAN benefits have therefore been extended to enable two or more LANs to be physically interconnected via forwarding devices (bridges or other switches) to form LAN segments or “segments” of so-called extended LANs. An extended LAN can operate as with a single LAN and can typically include the combined number of stations, geographical extent and so on of each segment. Extended LANs can also now operate according to virtual interconnection topologies that define reconfigurable active and inactive interconnection paths to form so-called virtual LANs (VLANs). The same general mechanism can also be applied to network types other than LANs or some combination.
The Institute of Electrical and Electronics Engineering (IEEE) standards 802.1, for example, provide physical constraints and spanning tree protocol (STP) topologies for implementing extended LANs, or other so-called inter-networks. STP (IEEE Std. 802.1D-1990, IEEE Standards for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges), for example, is a layer 2 link management protocol that automatically forces all participating bridges into an acyclic or loop free tree that spans the entire extended network. During initialization, or further upon automatic or user STP parameter change or fault-causing re-initialization, the distributed STP algorithm causes all participating bridges to exchange data messages called bridge protocol data units (“BPDUs”). This exchange determines a root bridge (“root”) as the logical center of the network, a closest (designated) bridge for each segment, and a shortest path to the root from each of the remaining (branch) bridges. Implementing STP also, for all branch bridges, automatically enables an active or forwarding state for the port having the shortest distance to the root (root port) and an outward connecting port (designated port), and automatically forces the remaining branch bridge ports (alternate ports) to a standby or blocking state. IEEE standards 802.1 are available via http://shop.ieee.org/store/ or otherwise from the Institute of Electrical and Electronics Engineering, and are hereby incorporated herein by reference.
The IEEE 802.1s (draft) standard extends the single spanning tree (SST) of IEEE 802.1D to enable the use of a LAN segment-specific STP, and IEEE 802.1w provides a rapid spanning tree protocol (RSTP) for faster convergence in establishing an STP-based configuration. Such standards are further extended by respective proprietary architectures from Cisco Systems, California, including Multiple Instance Spanning Tree Protocol (MISTP), Per-VLAN-Spanning Tree Protocol (PVST) and Rapid-Per-VLAN-Spanning Tree Protocol (rapid PVST or RPVST+). Among other features, IEEE 802.1s enables a set of Virual LANs (VLANs) to implement a separate STP instances and to enable the use of selectable STP instances, instance groups or associated instances or instance groups within or among LAN segments. (IEEE standards 802.1s and 802.1w are available via http://shop.ieee.org/store/ or otherwise from the Institute of Electrical and Electronics Engineering, and are hereby incorporated herein by reference. MISTP, PVST and RPVST+ are discussed, for example, by papers including a paper entitled Catalyst 6500 Series Cisco IOS Software Configuration Guide, 12.1E from Cisco Systems, which papers are hereby incorporated herein by reference.)
Using MSTP, each STP instance can have a topology independent of other spanning tree instances. Each participating bridge in a network portion including related STP instances (MST region) runs an internal spanning tree protocol and stores MSTP information for forming and selecting internal spanning tree (IST) instances. The MSTP information augments Common, Network-Wide STP information (CSTP) with the MSTP region information such that the resulting common and internal spanning tree instance set of the MSTP region operates as a CST subtree that appears to adjacent SST and MST regions as a single bridge. The STP, RSTP, and MSTP together elect a single bridge as the root of the CIST. Spanning tree information for each MSTP spanning tree instance (MSTI) is stored in an MSTP record (M-record) of an MSTP database and is encapsulated within MSTP BPDUs, the exchange of which is otherwise conducted in a similar manner as with STP information of SST implementations under IEEE 802.1d or per-LAN implementations under IEEE 802.1s.
Spanning trees computed by MSTP (M-trees) are active only within the MST region and merge with the IST at the boundary of the MST region to form the CST (e.g., see FIG. 1, a flow diagram illustrating a network implementing a conventional mixed STP and MSTP topology). MSTP otherwise operates in much the same way as SST, but on a per-instance basis. During initialization of each instance, or further upon automatic or user STP parameter change or fault causing re-initialization of an instance, a distributed STP algorithm causes participating bridges to exchange MST BPDUs, resulting in the determination of a root, backup or secondary root, per-region designated bridge and per-branch shortest path to the root; root and designated ports are also automatically enabled to a forwarding state and alternate ports are forced to a blocking state on a per-instance basis. Station addresses, however, are augmented with an extending instance identifier, e.g., 0, 1, 2 . . . , which identifier is stored as corresponding to the address and added to the MST BPDUs, and loops can be avoided using blocking states or by setting SST or MST region boundaries accordingly. Data packet transfer is also conducted in an otherwise consistent manner with IEEE 802.1d or IEEE 802.1s
It will be appreciated that IEEE 802.1s provides certain advantages over the SST of IEEE 802.1D, for example, in enabling the topology for each segment in an extended LAN to be separately determined according to segment-specific requisites. Cisco architectures including MISTP also provide even further benefits, such as by enabling selection of faster paths to particular stations, load balancing, backup or other applications, while PVST, rapid PVST and PVST+ enable more practically implemented fault tolerance and other features. However, the use of increasing numbers of MSTP or MISTP instances can become problematic, particularly with regard to computational requirements, station storage and potential delays resulting from switching among the instances. An increasing probability also exists that instances might be created that fail to provide any further benefit, among other problems. Accordingly, there is a need for a system and method that are capable of reducing processing or otherwise facilitating handling of multiple topology instances, such as MSTP and Cisco's MISTP.